package org.example.SolutionNew004;

import java.util.LinkedList;
import java.util.Queue;

public class GraphTheory001 {
    public static void main(String[] args) {
        GraphTheory001 gt=new GraphTheory001();
        char[][] geid=new char[][]{{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        System.out.println(gt.numIslands(geid));
    }

    //深度，空间复杂度高
    public int numIslands1(char[][] grid) {
        int res=0;
        int m=grid.length,n=grid[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    searchFromThere(grid,m,n,i,j);
                    res++;
                }
            }
        }
        return res;
    }

    public void searchFromThere(char[][] grid, int m,int n,int i, int j){
        if(i>=0&&i<m&&j>=0&&j<n&&grid[i][j]=='1'){
            grid[i][j]='0';
        }else{
            return;
        }
        searchFromThere(grid,m,n,i-1,j);
        searchFromThere(grid,m,n,i+1,j);
        searchFromThere(grid,m,n,i,j-1);
        searchFromThere(grid,m,n,i,j+1);
    }


    //广度，使用队列降空间复杂度
    public int numIslands2(char[][] grid) {
        int m=grid.length,n=grid[0].length;
        if(m==0||n==0) return 0;

        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    Queue<Integer> q=new LinkedList<>();
                    q.add(i*n+j);
                    while(!q.isEmpty()){
                        int x=q.poll();
                        int nr=x/n;
                        int nc=x%n;
                        grid[nr][nc]='0';
                        if(nr-1>=0&&grid[nr-1][nc]=='1'){
                            q.add((nr-1)*n+nc);
                            grid[nr-1][nc]='0';
                        }
                        if(nr+1<m&&grid[nr+1][nc]=='1'){
                            q.add((nr+1)*n+nc);
                            grid[nr+1][nc]='0';
                        }
                        if(nc-1>=0&&grid[nr][nc-1]=='1'){
                            q.add((nr)*n+nc-1);
                            grid[nr][nc-1]='0';
                        }
                        if(nc+1<n&&grid[nr][nc+1]=='1'){
                            q.add((nr)*n+nc+1);
                            grid[nr][nc+1]='0';
                        }
                    }
                    res++;
                }
            }
        }
        return res;
    }

    class UnionAll{
        int count;
        int[] parent;
        int[] rank;

        public UnionAll(char[][] grid){
            count=0;
            int m=grid.length,n=grid[0].length;
            parent=new int[m*n];
            rank=new int[m*n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(grid[i][j]=='1'){
                        count++;
                        parent[i*n+j]=i*n+j;
                    }
                    rank[i*n+j]=0;
                }
            }
        }


        public int find(int x){
            if(parent[x]!=x) parent[x]=find(parent[x]);
            return parent[x];
        }

        public void union(int x,int y){
            int xr=find(x);
            int yr=find(y);
            if(xr!=yr){
                if(rank[xr]<rank[yr]){
                    parent[xr]=yr;
                }else if(rank[xr]>rank[yr]){
                    parent[yr]=xr;
                }else{
                    //若深度相等，就随机取一个作为根
                    parent[yr]=xr;
                    rank[xr]++;
                }
                count--;
            }
        }

        public int getCount(){
            return count;
        }
    }

    //并查集
    public int numIslands(char[][] grid) {
        int m=grid.length,n=grid[0].length;
        if(grid==null||m==0||n==0) return 0;

        UnionAll u=new UnionAll(grid);
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    grid[i][j]='0';
                    if(i-1>=0&&grid[i-1][j]=='1'){
                        u.union(i*n+j,(i-1)*n+j);
                    }
                    if(j-1>=0&&grid[i][j-1]=='1'){
                        u.union(i*n+j,i*n+j-1);
                    }
                    if(j+1<n&&grid[i][j+1]=='1'){
                        u.union(i*n+j,i*n+j+1);
                    }
                    if(i+1<m&&grid[i+1][j]=='1'){
                        u.union(i*n+j,(i+1)*n+j);
                    }
                }
            }
        }
        return u.getCount();
    }
}
